﻿// 0905train01.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <limits>
#include <unordered_map>
#include <unordered_set>

using namespace std;

/*
 每个员工至少分1个月饼，但可以分多个
 单人分到最多月饼的个数是Max1，单人分到第二多月饼个数是Max2，Max1-Max2 <= 3
单人分到第n-1多月饼个数是Max(n-1)，单人分到第n多月饼个数是Max(n)，Max(n-1)- Max(n) <= 3
问有多少种分月饼的方法

挑选出m个非递减的数，要求相邻两个数的差值不超过3，这m个数的和为n，问一共有多少种挑选方式

输入
2 4
输出
2

4=1+3
4=2+2
注意: 1+3和3+1算一种分
 */
class Solution01
{
public:
    Solution01(int i_count, int total_sum)
    {
        //建dp数组
        //i [1,i_count] i_value[1,total_sum-i_count+1] sum[1,total_sum]
        vector<int>sum_vec(total_sum+1);
        vector<vector<int>>value_vec(total_sum - i_count + 2, sum_vec);
        vector<vector<vector<int>>>dynamic_vec(i_count + 1, value_vec);

        //初始化dp total_sum/i_count
        //[1][i_value][i_value]=1
        for (int i_value=1; i_value <=total_sum/i_count; i_value++)
        {
            dynamic_vec[1][i_value][i_value] = 1;
        }

        for (int i=1; i<=i_count-1; i++)
        {
	        for (int i_value=1; i_value<=total_sum-i_count+1; i_value++)
	        {
		        for (int sum=1; sum<=total_sum; sum++)
		        {
                    //dp[i+1][i_value+d][sum+i_value+d]+=dp[i][i_value][sum]
                    for (int d=0; d<=3; d++)
                    {

                        if (i_value+d<=total_sum-i_count+1 && sum+i_value+d<=total_sum)
                        {
                            dynamic_vec[i + 1][i_value + d][sum + i_value + d] += dynamic_vec[i][i_value][sum];
                        }

                    }

		        }
	        }
        }

        int result = 0;
        for (int i_value=1; i_value<=total_sum-i_count+1; i_value++)
        {
            result += dynamic_vec[i_count][i_value][total_sum];
        }
        cout << result;
        //Solution01
    }
};


/*
 A、B两个人玩抢7游戏
 游戏规则为A先报一个起始数字X (10 <= X <= 10000）B报下一个数字Y，(0<X-Y<3)
 A再报一个数字Z(0<Y-Z<3)，以此类推，直到其中一个抢到7，抢到7即为胜者
 在B赢得比赛的情况下，一共有多少种组合

输入描述
起始数字M，如100
10 <= M <= 10000

输出描述
B能赢得比赛的组合次数

输入
10
输出
1
只有一种赢的组合，A起始选择10，B接着选择9，A接着选择8，B接着选择7赢得胜利
 */
class Solution02
{
public:
    Solution02(long long num)
    {
        vector<long long>dynamic_a(num + 2);
        vector<long long>dynamic_b(num + 2);
        //A先从num开始报数
        dynamic_a[num] = 1;

        for (int i=num-1; i>=7; i--)
        {
            dynamic_b[i] = dynamic_a[i + 1] + dynamic_a[i + 2];
            dynamic_a[i] = dynamic_b[i + 1] + dynamic_b[i + 2];
        }
        cout << dynamic_b[7];
        //Solution02
    }
};

/*
 切成了每块大小都完全不同【奇数块】
 从“吃货”开始，轮流取披萨
 除了第一块披萨可以任意选取以外，其他都必须从缺口开始选。他俩选披萨的思路不同
“馋嘴”每次都会选最大块的披萨，而且“吃货"知道“馋嘴”的想法
已知披萨小块的数量以及每块的大小，求“吃货”能分得的最大的披萨大小的总和

输入描述
第1行为一个正整数奇数N，表示披萨小块数量。3 <= N <= 500。
接下来的第2行到第N+1行(共N行)，每行为一个正整数，表示第ì块披萨的大小。1 <= i <= N。
披萨小块从某一块开始，按照一个方向依次顺序编号为1~N

输出
“吃货”能分得的最大的披萨大小的总和

输入
5
8
2
10
5
7
输出
19
 */
class Solution03
{
public:
    Solution03(vector<int>&num_vec)
    {
        int v_size = num_vec.size();

        int ring_size = 2 * v_size;
        vector<int>ring_vec(ring_size);
        for (int i=0; i< ring_size; i++)
        {
            ring_vec[i] = num_vec[i % v_size];
        }
        //数组长度2*v_size
        vector<vector<int>>dynamic_vec(ring_size, vector<int>(ring_size));

        /*
         dp[i][j]表示区间[i,j]
		选择了i, i+1被选走, dp[i][j]=max(dp[i][j], dp[i+2][j]+num[i])
         */
        //初始化dp，只有一块能取到的最大值
        for (int start=0; start<ring_size; start++)
        {
            dynamic_vec[start][start] = ring_vec[start];
        }

        
        //start+d<=ring_size-1
        for (int d=3; d<=v_size; d+=2)
        {
	        for (int start=0; start<=ring_size-d; start++)
	        {
                int end = start + d-1;

                //result选择了start, other选start+1或end
                int range_start_max;
                if (ring_vec[start+1]>ring_vec[end])
                {
                    //选择start+1 区间[start+2,end]
                    range_start_max = dynamic_vec[start + 2][end] + ring_vec[start];
                }
                else
                {
                    //选择end 区间[start+1,end-1]
                    range_start_max = dynamic_vec[start + 1][end-1] + ring_vec[start];
                }
                dynamic_vec[start][end] = max(dynamic_vec[start][end], range_start_max);

                //result选择了end, other选择start或者end-1
                int range_end_max;
                if (ring_vec[start]>ring_vec[end-1])
                {
                    //选择start 区间[start+1, end-1]
                    range_end_max = dynamic_vec[start+1][end - 1] + ring_vec[end];
                }
                else
                {
                    //选择end-1 区间[start,end-2]
                    range_end_max = dynamic_vec[start][end - 2] + ring_vec[end];
                }
                dynamic_vec[start][end] = max(dynamic_vec[start][end], range_end_max);

	        }
        }

        int result = 0;
        for (int i=0; i<v_size; i++)
        {
            //cout << i << ' ' << i + v_size - 1 << endl;
            //cout << dynamic_vec[i][i + v_size - 1] << ' ';
        	result = max(result, dynamic_vec[i][i + v_size-1]);
        }

        cout << result;

        //Solution03
    }
};

class Solution13
{
public:
    Solution13(vector<long long>& num_vec)
    {
        int v_size = num_vec.size();

        int ring_size = 2 * v_size;
        vector<long long>ring_vec(ring_size);
        for (int i = 0; i < ring_size; i++)
        {
            ring_vec[i] = num_vec[i % v_size];
        }
        //数组长度2*v_size
        vector<vector<long long>>dynamic_vec(ring_size, vector<long long>(ring_size));

        /*
         dp[i][j]表示区间[i,j]
        选择了i, i+1被选走, dp[i][j]=max(dp[i][j], dp[i+2][j]+num[i])
         */
         //初始化dp，只有一块能取到的最大值
        for (int start = 0; start < ring_size; start++)
        {
            dynamic_vec[start][start] = ring_vec[start];
        }

        //区间长度，只能是奇数 d取到v_size，模拟环状结构
        //start+d<=ring_size-1
        for (int d = 3; d <= v_size; d += 2)
        {
            for (int start = 0; start <= ring_size - d; start++)
            {
                int end = start + d - 1;

                //result选择了start, other选start+1或end
                long long range_start_max;
                if (ring_vec[start + 1] > ring_vec[end])
                {
                    //选择start+1 区间[start+2,end]
                    range_start_max = dynamic_vec[start + 2][end] + ring_vec[start];
                }
                else
                {
                    //选择end 区间[start+1,end-1]
                    range_start_max = dynamic_vec[start + 1][end - 1] + ring_vec[start];
                }
                dynamic_vec[start][end] = max(dynamic_vec[start][end], range_start_max);

                //result选择了end, other选择start或者end-1
                long long range_end_max;
                if (ring_vec[start] > ring_vec[end - 1])
                {
                    //选择start 区间[start+1, end-1]
                    range_end_max = dynamic_vec[start + 1][end - 1] + ring_vec[end];
                }
                else
                {
                    //选择end-1 区间[start,end-2]
                    range_end_max = dynamic_vec[start][end - 2] + ring_vec[end];
                }
                dynamic_vec[start][end] = max(dynamic_vec[start][end], range_end_max);

            }
        }

        long long result = 0;
        for (int i = 0; i < v_size; i++)
        {
            //cout << i << ' ' << i + v_size - 1 << endl;
            //cout << dynamic_vec[i][i + v_size - 1] << ' ';
            result = max(result, dynamic_vec[i][i + v_size - 1]);
        }

        cout << result;

        //Solution03
    }
};

int main()
{
	{
        int v_size;
        cin >> v_size;

        vector<long long>num_vec(v_size);

        for (int i=0; i<v_size; i++)
        {
            cin >> num_vec[i];
        }

        for (auto&num:num_vec)
        {
            cout << num << ',';
        }
        //Solution03 solu(num_vec);

        return 0;
	}
	{
        long long M;
        cin >> M;
        Solution02 solu(M);

        return 0;
	}
    int i_count = 2, total_sum = 4;
    //int i_count, total_sum;
    //cin >> i_count >> total_sum;
    Solution01 solu(i_count, total_sum);

}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
